package org.opens.javaskill.algorithm.sort;

import cn.hutool.core.collection.CollectionUtil;
import cn.hutool.core.util.StrUtil;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class BubbleSort {

    private static int[] arr = {123, 45, 64, 23, 651, 424, 872, 168, 23432};

    /**
     * 功能: 冒泡排序的实例-最简单的排序, 相邻的元素两两交换;
     */
    @Test
    public void testBubbleSort() {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    arr[i] = arr[i] ^ arr[j];
                    arr[j] = arr[i] ^ arr[j];
                    arr[i] = arr[i] ^ arr[j];
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 功能: 插入排序的实例;
     * 说明:
     * <pre>
     *     1. 算法流程如下-将该算法想象为对手中的扑克牌进行排序, 但是有一些限制:
     *      - 必须从最右边或者最左边开始比较;
     *      - 每次比较时只能交换相邻的两张牌;
     *     2. 用断点跟一下这个算法的过程就可以理解了.
     * </pre>
     */
    @Test
    public void testInsertSort() {
        int tmp, i ,j;
        for (i = 1; i < arr.length; i++) {
            tmp = arr[i];
            for (j = i - 1; j >= 0 && arr[j] > tmp; j--) {
                arr[j + 1] = arr[j];
            }
            arr[j + 1] = tmp;
        }
        System.out.println(Arrays.toString(arr));
    }

    @Test
    public void quickSortTest() {
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 功能: 快速排序的实现方法
     * @param arr       待排序数组
     * @param left_     排序起始左坐标
     * @param right_    排序起始右坐标
     */
    public static void quickSort(int[] arr, int left_, int right_) {
        int left = left_;
        int right = right_;
        int tmp = 0;
        if (left < right) {
            tmp = arr[left];
            while (left != right) {
                while (right > left && arr[right] >= tmp) {
                    right--;
                }
                arr[left] = arr[right];
                while (right > left && arr[left] <= tmp) {
                    left++;
                }
                arr[right] = arr[left];
            }
            arr[right] = tmp;
            quickSort(arr, left_, left - 1);
            quickSort(arr, right + 1, right_);
        }
    }

}
